﻿public class Solution {
    public bool RepeatedSubstringPattern(string s)
    {
        // 获取next数组
        int[] next = GetNext(s);

        int n = s.Length - next[s.Length - 1];
        
        if (next[s.Length - 1] != 0 && next[s.Length - 1] % n == 0)
        {
            return true;
        }
        return false;
    }

    private int[] GetNext(string s)
    {
        int[] next = new int[s.Length];
        int j = 0;
        next[j] = j;

        for (int i = 1; i < s.Length; i++)
        {
            while (j > 0 && s[i] != s[j])
            {
                j = next[j-1];
            }

            if (s[i] == s[j])
            {
                j++;
            }
            next[i] = j;
        }

        return next;
    }

    public static void Main(string[] args)
    {
        string s = "ababba";

        Solution solution = new Solution();
        bool res = solution.RepeatedSubstringPattern(s);
        Console.WriteLine(res);
    }
}